DP M - 西尾泰和の外部脳

DP M

https://gyazo.com/7f00d3569b97262049eab2547f73d1ad

分配の数え上げ問題

DP合流時の足し算が重たい

累積和を事前に求める

素朴な解法、これで最後以外のサンプルは通る

code:python

def solve(N, K, XS):

table = 0 * (K + 1)

for i in range(XS0 + 1):

tablei = 1

for i in range(1, N):

v = 0

newtable = 0 * (K + 1)

for j in range(K + 1):

v = 0

for k in range(XSi + 1):

if j - k < 0:

break

v += tablej - k

v %= MOD

newtablej = v

table = newtable

return tableK

シンプルなもので何がいけないかというと足し算のループなので、事前に累積和を求める

code:python

def solve(N, K, XS):

table = 0 * (K + 1)

for i in range(XS0 + 1):

tablei = 1

for i in range(1, N):

v = 0

newtable = 0 * (K + 1)

accum = 0 * (K + 1)

acc = 0

for j in range(K + 1):

acc += tablej

accumj = acc

for j in range(K + 1):

v = accumj

k = j - XSi - 1

if k >= 0:

v -= accumk

newtablej = v % MOD

table = newtable

return tableK